package data_structure.tree;

public class BinaryTree {
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    //先序遍历
    public void pre(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.getId());
        pre(root.getLeft());
        pre(root.getRight());
    }

    //增加节点
    public Boolean add(int node) {

        if (null == root) {
            root = new TreeNode(node, null);

            return true;
        }
        return addNode(node, root);
    }

    private Boolean addNode(int node, TreeNode root) {
        if (root.getLeft() == null) {
            root.setLeft(new TreeNode(node, root));
            return true;
        }
        if (root.getRight() == null) {
            root.setRight(new TreeNode(node, root));
            return true;
        }
        if (root.getParent() != null) {
            if(root.getParent().getRight().getLeft() == null) {
                root.getParent().getRight().setLeft(new TreeNode(node, root.getParent().getRight()));
                return true;
            }
            if(root.getParent().getRight().getRight() == null) {
                root.getParent().getRight().setRight(new TreeNode(node, root.getParent().getRight()));
                return true;
            }
        }


        return addNode(node, root.getLeft());
    }




    static class TreeNode {
        private int id;
        private TreeNode left;
        private TreeNode right;
        private TreeNode parent;

        public TreeNode(int id) {
            this.id = id;
        }

        public TreeNode(int id, TreeNode parent) {
            this.id = id;
            this.parent = parent;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
